package com.xzx.algorithms.leetcode;

import java.util.Arrays;
import java.util.HashMap;

/**
 * 两数之和
 * 给定一个整数数组 和 一个整数目标值，请在数组中找出 和为目标值的两个整数的下标
 * 假设每种输入只对应一个答案
 * @author xinzhixuan
 * @version 1.0
 * @date 2021-07-12 12:55 下午
 */
public class D0001_SumOfTwoNumber {
    public static void main(String[] args) {
        int[] nums  = {3, 2, 4};
        int target = 6;

        System.out.println(Arrays.toString(twoSum3(nums, target)));
    }

    /**
     * O(n^2)的复杂度
     * @param nums .
     * @param target .
     * @return .
     */
    public static int[] twoSum(int[] nums, int target) {
        int[] indexs = new int[]{-1, -1};
        for (int firstIndex = 0; firstIndex < nums.length - 1; firstIndex ++) {
            for (int secondIndex = firstIndex + 1; secondIndex < nums.length; secondIndex ++) {
                if (nums[firstIndex] + nums[secondIndex] == target) {
                    indexs = new int[]{firstIndex, secondIndex};
                }
            }
        }
        return indexs;
    }

    /**
     * 用空间换时间. 这种算法最差需要把整个数组算完
     * @param nums .
     * @param target .
     * @return .
     */
    public static int[] twoSum2(int[] nums, int target) {
        int[] indexs = new int[]{-1, -1};
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int firstIndex = 0; firstIndex < nums.length; firstIndex ++) {
            int remain = target - nums[firstIndex];
            Integer secondIndex = map.get(remain);
            if (secondIndex == null) {
                map.put(nums[firstIndex], firstIndex);
            } else {
                return new int[]{firstIndex, secondIndex};
            }
        }
        return indexs;
    }

    /**
     * 从两边开始一起算，二分的思想
     * @param nums .
     * @param target .
     * @return .
     */
    public static int[] twoSum3(int[] nums, int target) {
        int[] indexs = new int[]{-1, -1};
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int firstIndex = 0, secondIndex = nums.length - 1; firstIndex <= secondIndex; firstIndex ++, secondIndex--) {
            int remain = target - nums[firstIndex];
            Integer idx = map.get(remain);
            if (idx == null) {
                map.put(nums[firstIndex], firstIndex);
            } else {
                return new int[]{firstIndex, idx};
            }

            remain = target - nums[secondIndex];
            idx = map.get(remain);
            if (idx == null) {
                map.put(nums[secondIndex], secondIndex);
            } else {
                return new int[]{idx, secondIndex};
            }
        }
        return indexs;
    }
}
